{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Path in Binary Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestPathBinaryMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二进制矩阵中的最短路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n x n</code> 的二进制矩阵 <code>grid</code> 中，返回矩阵中最短 <strong>畅通路径</strong> 的长度。如果不存在这样的路径，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>二进制矩阵中的 畅通路径 是一条从 <strong>左上角</strong> 单元格（即，<code>(0, 0)</code>）到 右下角 单元格（即，<code>(n - 1, n - 1)</code>）的路径，该路径同时满足下述要求：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>路径途经的所有单元格的值都是 <code>0</code> 。</li>\n",
    "\t<li>路径中所有相邻的单元格应当在 <strong>8 个方向之一</strong> 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>畅通路径的长度</strong> 是该路径途经的单元格总数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/18/example1_1.png\" style=\"width: 500px; height: 234px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,1],[1,0]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/18/example2_1.png\" style=\"height: 216px; width: 500px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,0,0],[1,1,0],[1,1,0]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,0,0],[1,1,0],[1,1,0]]\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-path-in-binary-matrix](https://leetcode.cn/problems/shortest-path-in-binary-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-path-in-binary-matrix](https://leetcode.cn/problems/shortest-path-in-binary-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[1,0]]', '[[0,0,0],[1,1,0],[1,1,0]]', '[[1,0,0],[1,1,0],[1,1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]:\n",
    "            return -1\n",
    "        n = len(grid)\n",
    "        grid[0][0] = 1\n",
    "        q = deque([(0, 0)])\n",
    "        ans = 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                if i == j == n - 1:\n",
    "                    return ans\n",
    "                for x in range(i - 1, i + 2):\n",
    "                    for y in range(j - 1, j + 2):\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\n",
    "                            grid[x][y] = 1\n",
    "                            q.append((x, y))\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        size = len(grid)\n",
    "        if grid[0][0] == 1 or grid[size-1][size-1] == 1:\n",
    "            return -1\n",
    "        if len(grid) == 1:\n",
    "            return 1\n",
    "        step = 1\n",
    "        q = collections.deque()\n",
    "        visited = {}\n",
    "        q.append((0, 0))\n",
    "        visited[(0,0)] = True\n",
    "        while q:\n",
    "            for t in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                i, j = cur[0], cur[1]\n",
    "                for x in [(i+1, j), (i, j+1), (i+1, j+1), (i-1, j+1), (i-1, j), (i-1, j-1), (i, j-1), (i+1, j-1)]:\n",
    "                    if -1 < x[0] < size and -1 < x[1] < size and grid[x[0]][x[1]] == 0 and not visited.get((x[0],x[1])):\n",
    "                        if x[0]==size-1 and x[1]==size-1:\n",
    "                            return step+1\n",
    "                        q.append(x)\n",
    "                        visited[(x[0],x[1])] = True\n",
    "            step += 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] != 0:\n",
    "            return -1\n",
    "        length = len(grid)\n",
    "        if length == 1:\n",
    "            return 1\n",
    "        que = deque()\n",
    "        visited = {}\n",
    "        que.appendleft((0,0))\n",
    "        visited[(0,0)] = True\n",
    "        start = 1\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                ind, con = que.pop()\n",
    "                for pos_h, pos_v in [(-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1)]:\n",
    "                    new_ind = ind + pos_h\n",
    "                    new_con = con + pos_v\n",
    "                    if 0 <= new_ind < length and 0 <= new_con < length and grid[new_ind][new_con] == 0 and not visited.get((new_ind, new_con)):\n",
    "                        if new_ind == length - 1 and new_con == length - 1:\n",
    "                            return start + 1\n",
    "                        que.appendleft((new_ind, new_con))\n",
    "                        visited[(new_ind, new_con)] = True\n",
    "            start += 1\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]==1:return -1\n",
    "        res=1\n",
    "        queue=deque()\n",
    "        queue.append((0,0))\n",
    "        grid[0][0]=1\n",
    "        tmp=[[-1,-1],[-1,1],[1,-1],[1,1],[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                x,y=queue.popleft()\n",
    "                if x==len(grid)-1 and y==len(grid[0])-1:return res\n",
    "                for l,r in tmp:\n",
    "                    a,b=x+l,y+r\n",
    "                    if 0<=a<len(grid) and 0<=b<len(grid[0]) and grid[a][b]==0:\n",
    "                        grid[a][b]=1\n",
    "                        queue.append((a,b))\n",
    "            res+=1\n",
    "        return -1\n",
    "\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1:\n",
    "            return -1\n",
    "        grid[0][0] = 1\n",
    "        step = 0\n",
    "        dq = deque([(0, 0)])\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        while dq:\n",
    "            step += 1\n",
    "            size = len(dq)\n",
    "            for _ in range(size):\n",
    "                i, j = dq.popleft()\n",
    "                if i == m - 1 and j == n - 1:\n",
    "                    return step\n",
    "                for di in (-1, 0, 1):\n",
    "                    for dj in (-1, 0, 1):\n",
    "                        if di == 0 and dj == 0:\n",
    "                            continue\n",
    "                        ni, nj = i + di, j + dj\n",
    "                        if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 0:\n",
    "                            grid[ni][nj] = 1\n",
    "                            dq.append((ni, nj))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]:\n",
    "            return -1\n",
    "        n = len(grid)\n",
    "        grid[0][0] = 1\n",
    "        q = deque([(0, 0)])\n",
    "        ans = 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):#遍历完所有的情况，寻找最近的一个点\n",
    "                i, j = q.popleft()\n",
    "                if i == j == n - 1:\n",
    "                    return ans\n",
    "                for x in range(i - 1, i + 2):\n",
    "                    for y in range(j - 1, j + 2):\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\n",
    "                            grid[x][y] = 1\n",
    "                            q.append((x, y))\n",
    "            ans += 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]:\n",
    "            return -1\n",
    "        n = len(grid)\n",
    "        grid[0][0] = 1\n",
    "        q = deque([(0, 0)])\n",
    "        ans = 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                if i == j == n - 1:\n",
    "                    return ans\n",
    "                for x in range(i - 1, i + 2):\n",
    "                    for y in range(j - 1, j + 2):\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\n",
    "                            grid[x][y] = 1\n",
    "                            q.append((x, y))\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # bfs 广度优先是一层一层的 所以先搜索到的 就是最短的\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        cur=1\n",
    "        if grid[0][0]==1 or grid[n-1][n-1]==1:\n",
    "            return -1\n",
    "        if n==1:\n",
    "            return 1\n",
    "        \n",
    "        que=collections.deque()\n",
    "        que.append((0,0))\n",
    "        while que:\n",
    "            # 遍历在每一个位置可以走的所有地点\n",
    "            for _ in range(len(que)):\n",
    "                r,s=que.popleft()\n",
    "                grid[r][s]=1\n",
    "                for x,y in [(r-1,s-1),(r,s-1),(r-1,s),(r+1,s+1),(r,s+1),(r+1,s),(r-1,s+1),(r+1,s-1)]:\n",
    "                    if 0<=x<n and 0<=y<n and grid[x][y]==0:\n",
    "                        que.append((x,y))\n",
    "                        grid[x][y]=1\n",
    "                        if x==n-1 and y==n-1:\n",
    "                            return cur+1\n",
    "            cur+=1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1:\n",
    "            return -1 \n",
    "\n",
    "        def g(x, y):\n",
    "            return max(n - x, n - y)\n",
    "\n",
    "        n = len(grid)\n",
    "        dist = [[inf] * n for _ in range(n)]\n",
    "        dist[0][0] == 1\n",
    "        q = [(1, 1, 0, 0)]\n",
    "        while q:\n",
    "            _, d, x, y = heappop(q) \n",
    "            if x == y == n - 1:\n",
    "                 return d\n",
    "            d += 1\n",
    "            for dx in (-1, 0, 1):\n",
    "                for dy in (-1, 0, 1):\n",
    "                    if dx or dy:\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if not (0 <= nx < n and 0 <= ny < n):\n",
    "                            continue\n",
    "                        if grid[nx][ny] == 0 and d < dist[nx][ny]:\n",
    "                            dist[nx][ny] = d \n",
    "                            heappush(q, (dist[nx][ny] + g(nx, ny), dist[nx][ny], nx, ny))\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]:\n",
    "            return -1\n",
    "        n = len(grid)\n",
    "        grid[0][0] = 1\n",
    "        q = deque([(0, 0)])\n",
    "        ans = 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                if i == j == n - 1:\n",
    "                    return ans\n",
    "                for x in range(i - 1, i + 2):\n",
    "                    for y in range(j - 1, j + 2):\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\n",
    "                            grid[x][y] = 1\n",
    "                            q.append((x, y))\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]:\n",
    "            return -1\n",
    "        n = len(grid)\n",
    "        grid[0][0] = 1\n",
    "        q = deque([(0, 0)])\n",
    "        ans = 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                if i == j == n - 1:\n",
    "                    return ans\n",
    "                for x in range(i - 1, i + 2):\n",
    "                    for y in range(j - 1, j + 2):\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\n",
    "                            grid[x][y] = 1\n",
    "                            q.append((x, y))\n",
    "            ans += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        #copy\n",
    "        if grid[0][0]:\n",
    "            return -1\n",
    "        n = len(grid)\n",
    "        grid[0][0] =1\n",
    "        q= deque([(0,0)])\n",
    "        ans = 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i,j = q.popleft()\n",
    "                if i ==j == n-1:\n",
    "                    return ans\n",
    "                for x in range(i-1,i+2):\n",
    "                    for y in range(j-1,j+2):\n",
    "                        if 0<=x<n and 0<=y<n and grid[x][y] ==0:\n",
    "                            grid[x][y] =1\n",
    "                            q.append((x,y))\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        def g(x, y):\n",
    "            return max(n - x, n - y)\n",
    "        n = len(grid)\n",
    "        dist = [[inf] * n for _ in range(n)]\n",
    "        if grid[0][0] == 1:\n",
    "            return -1 \n",
    "        dist[0][0] == 1\n",
    "        q = [(1, 1,0,0)]\n",
    "        while q:\n",
    "            _, d, x, y = heappop(q) \n",
    "            if (x, y) == (n-1, n-1): return d\n",
    "            for dx in (-1,0,1):\n",
    "                for dy in (-1,0,1):\n",
    "                    if not (dx == 0 and dy == 0):\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if not (0 <= nx < n and 0 <= ny < n): continue\n",
    "                        if grid[nx][ny] == 0 and d + 1 < dist[nx][ny]:\n",
    "                            dist[nx][ny] = 1 + d \n",
    "                            heappush(q, (dist[nx][ny] + g(nx, ny), dist[nx][ny], nx, ny))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        dire = [(0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1)]\n",
    "        N = len(grid)\n",
    "\n",
    "        visited = [[False] * N for _ in range(N)]\n",
    "        q = deque([(0,0,1)])\n",
    "        visited[0][0] = True\n",
    "        while q:\n",
    "            x, y, l = q.popleft()\n",
    "            if x==N-1 and y==N-1:\n",
    "                return l if grid[x][y]==0 else -1\n",
    "            if grid[x][y] == 1:\n",
    "                continue\n",
    "            for dx, dy in dire:\n",
    "                xx, yy = x+dx, y+dy\n",
    "                if xx<0 or xx>=N or yy<0 or yy>=N or visited[xx][yy]:\n",
    "                    continue\n",
    "                q.append((xx, yy, l+1))\n",
    "                visited[xx][yy] = True\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import deque\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]==1:\n",
    "            return -1\n",
    "\n",
    "        row_len = len(grid)\n",
    "        col_len = len(grid[0])\n",
    "        visit = [[False for _ in range(col_len)] for _ in range(row_len)]\n",
    "        queue = deque()\n",
    "        queue.append((0,0))\n",
    "        visit[0][0] = True\n",
    "        step = 0\n",
    "        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]\n",
    "        while(len(queue)>0):\n",
    "            step+=1\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                i,j = queue.popleft()\n",
    "                if i==row_len-1 and j==col_len-1:\n",
    "                    return step\n",
    "                for m,n in dirs:\n",
    "                    next_i,next_j = i+m,j+n \n",
    "                    if  next_i<0 or next_i>=row_len or next_j<0 or next_j>=col_len:\n",
    "                        continue\n",
    "                    if visit[next_i][next_j] or grid[next_i][next_j]==1:\n",
    "                        continue\n",
    "                    queue.append((next_i,next_j))\n",
    "                    visit[next_i][next_j]=True\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestPathBinaryMatrix(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if grid[-1][-1]==1 or grid[0][0]==1:\n",
    "            return -1\n",
    "        dirs=[(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1),]\n",
    "        grid[0][0]=1\n",
    "        deq=deque()\n",
    "        tlen=len(grid)\n",
    "        deq.append(((0,0),1))\n",
    "        while deq:\n",
    "            tmp=deq.popleft()\n",
    "            for dir in dirs:\n",
    "                x,y=tmp[0][0]+dir[0],tmp[0][1]+dir[1]\n",
    "                if 0<=x<tlen and 0<=y<tlen and grid[x][y]==0:\n",
    "                    deq.append(((x,y),tmp[1]+1))\n",
    "                    grid[x][y]=tmp[1]+1\n",
    "\n",
    "        return grid[-1][-1] if grid[-1][-1]!=0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or grid[0][0] == 1: return -1\n",
    "        directions = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [1, 1], [-1, 1], [1, -1]]\n",
    "        n = len(grid)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        dp[0][0] = 1\n",
    "        deque = collections.deque([(0, 0)])\n",
    "        while deque:\n",
    "            x, y = deque.popleft()\n",
    "            if x == y == n-1:\n",
    "                return dp[x][y]\n",
    "            for dx, dy in directions:\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                if 0 <= new_x < n and 0 <= new_y < n and grid[new_x][new_y] == 0 and dp[new_x][new_y] == 0:\n",
    "                    dp[new_x][new_y] = dp[x][y] + 1\n",
    "                    deque.append((new_x, new_y))\n",
    "        return -1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]:\n",
    "            return -1\n",
    "        n = len(grid)\n",
    "        grid[0][0] = 1\n",
    "        q = deque([(0, 0)])\n",
    "        ans = 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                if i == j == n - 1:\n",
    "                    return ans\n",
    "                for x in range(i - 1, i + 2):\n",
    "                    for y in range(j - 1, j + 2):\n",
    "                        if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\n",
    "                            grid[x][y] = 1\n",
    "                            q.append((x, y))\n",
    "            ans += 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        ans = [[0x7fffffff for i in range(n)]for j in range(n)]\n",
    "        if grid[0][0] == 1:\n",
    "            return -1\n",
    "        que = collections.deque()\n",
    "        que.append([0,0])\n",
    "        ans[0][0] = 1\n",
    "        dire=[[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "        while que:\n",
    "            x,y = que.popleft()\n",
    "            for i,j in dire:\n",
    "                if n> x + i > -1 and n> y + j > -1:\n",
    "                    if grid[x+i][y+j] == 0 and ans[x+i][y + j] > ans[x][y] + 1:\n",
    "                        ans[x+i][y+j] = ans[x][y] + 1\n",
    "                        que.append([x+i,y+j])\n",
    "        if ans[-1][-1] == 0x7fffffff:\n",
    "            return -1\n",
    "        return ans[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1:\n",
    "            return -1\n",
    "        n = len(grid)\n",
    "        dist = [[inf] * n for _ in range(n)]\n",
    "        dist[0][0] = 1\n",
    "        queue = deque([(0, 0)])\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            if x == y == n - 1:\n",
    "                return dist[x][y]\n",
    "            for dx in range(-1, 2):\n",
    "                for dy in range(-1, 2):\n",
    "                    if x + dx < 0 or x + dx >= n or y + dy < 0 or y + dy >= n: # 越界\n",
    "                        continue\n",
    "                    if (grid[x + dx][y + dy] == 1 or dist[x + dx][y + dy] <= dist[x][y] + 1): # 单元格值不为 0 或已被访问\n",
    "                        continue\n",
    "                    dist[x + dx][y + dy] = dist[x][y] + 1\n",
    "                    queue.append((x + dx, y + dy))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] :\n",
    "            return -1\n",
    "        # 广搜\n",
    "        n = len(grid)\n",
    "        q = [(0, 0)]\n",
    "        grid[0][0] = 1\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            cnt += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                if i == j == n - 1:\n",
    "                    return cnt\n",
    "                for i2, j2 in (i+1, j), (i-1, j), (i, j+1), (i, j-1), (i+1, j+1), (i-1, j-1), (i-1, j+1), (i+1, j-1):\n",
    "                    if -1<i2<n and -1<j2<n and not grid[i2][j2]:\n",
    "                        grid[i2][j2] = 1\n",
    "                        q.append((i2, j2))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        l=len(grid)\n",
    "        if grid[0][0]==1 or grid[l-1][l-1]==1:return -1\n",
    "        if l==1:return 1\n",
    "        if l==2:return 2\n",
    "        m=[[0 for i in range(l)] for j in range(l)]\n",
    "        m[0][0] = 1\n",
    "        q = deque([(0,0)])\n",
    "        while q:\n",
    "            i,j = q.popleft()\n",
    "            if i == j == l - 1:return m[i][j]\n",
    "            if j < l-1:\n",
    "                if m[i][j+1] == 0 and grid[i][j+1] == 0:\n",
    "                    m[i][j+1] = m[i][j] + 1\n",
    "                    q.append((i,j+1))\n",
    "            if j > 0:\n",
    "                if m[i][j-1] == 0 and grid[i][j-1] == 0:\n",
    "                    m[i][j-1] = m[i][j] + 1\n",
    "                    q.append((i,j-1))\n",
    "            if i > 0:\n",
    "                if m[i-1][j] == 0 and grid[i-1][j] == 0:\n",
    "                    m[i-1][j] = m[i][j] + 1\n",
    "                    q.append((i-1,j))\n",
    "                if j > 0:\n",
    "                    if m[i-1][j-1] == 0 and grid[i-1][j-1] == 0:\n",
    "                        m[i-1][j-1] = m[i][j] + 1\n",
    "                        q.append((i-1,j-1))\n",
    "                if j < l-1:\n",
    "                    if m[i-1][j+1] == 0 and grid[i-1][j+1] == 0:\n",
    "                        m[i-1][j+1] = m[i][j] + 1\n",
    "                        q.append((i-1,j+1))\n",
    "            if i < l-1:\n",
    "                if m[i+1][j] == 0 and grid[i+1][j] == 0:\n",
    "                    m[i+1][j] = m[i][j] + 1\n",
    "                    q.append((i+1,j))\n",
    "                if j > 0:\n",
    "                    if m[i+1][j-1] == 0 and grid[i+1][j-1] == 0:\n",
    "                        m[i+1][j-1] = m[i][j] + 1\n",
    "                        q.append((i+1,j-1))\n",
    "                if j < l-1:\n",
    "                    if m[i+1][j+1] == 0 and grid[i+1][j+1] == 0:\n",
    "                        m[i+1][j+1] = m[i][j] + 1\n",
    "                        q.append((i+1,j+1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        if not grid or not grid[0] or grid[0][0] == 1 or grid[-1][-1] == 1:\n",
    "            return -1\n",
    "        \n",
    "        from collections import deque\n",
    "        n = len(grid)\n",
    "\n",
    "        directions = []\n",
    "        for i in range(-1, 2):\n",
    "            for j in range(-1, 2):\n",
    "                if i == 0 and j == 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    directions.append((i, j))\n",
    "        \n",
    "        visited = [[0] * n for i in range(n)]\n",
    "\n",
    "        visited[0][0] = 1\n",
    "        que = deque([(0, 0)])\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while que:\n",
    "\n",
    "            size = len(que)\n",
    "            res += 1\n",
    "\n",
    "            for i in range(size):\n",
    "                x, y = que.popleft()\n",
    "\n",
    "                if x == n - 1 and y == n - 1:\n",
    "                    return res\n",
    "\n",
    "                for ox, oy in directions:\n",
    "\n",
    "                    nx, ny = x + ox, y + oy\n",
    "\n",
    "                    if nx >= 0 and nx < n and ny >= 0 and ny < n and visited[nx][ny] == 0 and grid[nx][ny] == 0:\n",
    "                        visited[nx][ny] = 1\n",
    "                        que.append((nx, ny))\n",
    "\n",
    "        return -1\n",
    "                        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] :\n",
    "            return -1\n",
    "        # 广搜\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        q = [(0, 0)]\n",
    "        grid[0][0] = 1\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            cnt += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                if i == m - 1 and j == n - 1:\n",
    "                    return cnt\n",
    "                for i2, j2 in (i+1, j), (i-1, j), (i, j+1), (i, j-1), (i+1, j+1), (i-1, j-1), (i-1, j+1), (i+1, j-1):\n",
    "                    if -1<i2<m and -1<j2<n and not grid[i2][j2]:\n",
    "                        grid[i2][j2] = 1\n",
    "                        q.append((i2, j2))\n",
    "            \n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1: return -1\n",
    "        n = len(grid)\n",
    "        stack = [[0,0,1]] # 用来作为备忘录，位置+目前走的格数\n",
    "        ans = 10001\n",
    "        while stack:\n",
    "            cur_node = stack[0]\n",
    "            i, j, depth = cur_node\n",
    "            # 剪枝操作\n",
    "            if grid[i][j] == 1:\n",
    "                stack.pop(0)\n",
    "                continue\n",
    "            if i == n-1 and j == n-1 and grid[i][j] == 0: ans = min(ans,depth)\n",
    "            if i == n-1 and j == n-1 and grid[i][j] == 0: ans = min(ans,depth)\n",
    "            if i-1 >= 0 and j-1 >= 0 and grid[i-1][j-1] == 0:\n",
    "                stack.append([i-1,j-1,depth+1])\n",
    "            if i-1 >= 0 and grid[i-1][j] == 0:\n",
    "                stack.append([i-1,j,depth+1])\n",
    "            if i-1 >= 0 and j+1 < n  and grid[i-1][j+1] == 0:\n",
    "                stack.append([i-1,j+1,depth+1])\n",
    "            if j-1 >= 0 and grid[i][j-1] == 0:\n",
    "                stack.append([i,j-1,depth+1])\n",
    "            if j+1 < n and grid[i][j+1] == 0:\n",
    "                stack.append([i,j+1,depth+1])\n",
    "            if i+1 < n and j-1 >= 0 and grid[i+1][j-1] == 0:\n",
    "                stack.append([i+1,j-1,depth+1])\n",
    "            if i+1 < n and grid[i+1][j] == 0:\n",
    "                stack.append([i+1,j,depth+1])\n",
    "            if i+1 < n and j+1 < n and grid[i+1][j+1] == 0:\n",
    "                stack.append([i+1,j+1,depth+1])\n",
    "            grid[i][j] = 1\n",
    "            stack.pop(0)\n",
    "        if ans == 10001: return -1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid == [] or grid[0][0]==1:\n",
    "            return -1\n",
    "        Q = [(0,0)]\n",
    "        grid[0][0] = 1\n",
    "        n = len(grid)\n",
    "        ans = 0\n",
    "        while Q!=[]:\n",
    "            index = []\n",
    "            ans += 1\n",
    "            while Q!=[]:\n",
    "                if Q[0] == (n-1,n-1):\n",
    "                    return ans\n",
    "                (i,j) = Q[0]\n",
    "                Q.pop(0)\n",
    "                for (x,y) in [(i+1,j+1),(i+1,j),(i,j+1),(i-1,j+1),(i+1,j-1),(i-1,j),(i,j-1),(i-1,j-1)]:\n",
    "                    if x in range(n) and y in range(n) and grid[x][y] == 0 and (x,y) not in index:\n",
    "                        #print(x,y)\n",
    "                        index.append((x,y))\n",
    "                        #print(ans)\n",
    "                        grid[x][y] = 1\n",
    "            Q = index\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        ans = 99999999\n",
    "        if grid[0][0] == 1:\n",
    "            return -1\n",
    "        dp = [[-1 for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        dp[0][0] = 1\n",
    "        q = collections.deque()\n",
    "        q.append([0, 0, 1])\n",
    "        while len(q) > 0:\n",
    "            di = q.popleft()\n",
    "            x = di[0]\n",
    "            y = di[1]\n",
    "            v = di[2]\n",
    "            #print(x, y)\n",
    "            if x == len(grid) - 1 and y == len(grid[0]) - 1:\n",
    "                #print(v)\n",
    "                ans = min(ans, v)\n",
    "            for i in range(-1, 2):\n",
    "                for j in  range(-1, 2):\n",
    "                    if 0 <= x + i < len(grid) and 0 <= y + j < len(grid[0]) and grid[i + x][j + y] == 0 and dp[i + x][j + y] == -1:\n",
    "                        dp[i + x][j + y] = 1\n",
    "                        q.append([x + i, y + j, v + 1])\n",
    "        if ans == 99999999:\n",
    "            ans = -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid[0]),len(grid)\n",
    "        if grid[0][0]==1:\n",
    "            return -1\n",
    "        \n",
    "        v = [[1 for i in range(m)]for _ in range(n)]\n",
    "        v[0][0] = 0\n",
    "        q = [[0,0]]\n",
    "        d = [[0,1],[1,0],[0,-1],[-1,0],[1,1],[-1,-1],[1,-1],[-1,1]]\n",
    "        s = 1\n",
    "        while q:\n",
    "            print(q)\n",
    "            for _ in range(len(q)):\n",
    "                cq = q[0]\n",
    "                del q[0]\n",
    "                if cq==[m-1,n-1]:\n",
    "                    return s \n",
    "                cx,cy = cq[0],cq[1]\n",
    "                v[cx][cy] = 0\n",
    "                for i in range(8):\n",
    "                    nx,ny = cx+d[i][0],cy+d[i][1]\n",
    "                    if 0<=nx<m and 0<=ny<n and grid[nx][ny]==0 and v[nx][ny]:\n",
    "                        q.append([nx,ny])\n",
    "                        v[nx][ny] = 0\n",
    "            s = s+1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] > 0:\n",
    "            return -1\n",
    "        n = len(grid)\n",
    "        dist = [[n*n for _ in range(n)] for _ in range(n)]\n",
    "        dist[0][0] = 1\n",
    "        q = [(0, 0)]\n",
    "\n",
    "        while q:\n",
    "            x, y = q.pop(0)\n",
    "            if x == y == n - 1:\n",
    "                return dist[x][y]\n",
    "            for dx in range(-1, 2):\n",
    "                for dy in range(-1, 2):\n",
    "                    if x + dx < 0 or dx + x >= n or y + dy < 0 or y + dy >= n:\n",
    "                        continue\n",
    "                    if (grid[x + dx][y + dy]) == 1 or dist[x + dx][y + dy] <= dist[x][y] + 1:\n",
    "                        continue\n",
    "                    dist[x + dx][y + dy] = dist[x][y] + 1\n",
    "                    q.append((x + dx, y + dy))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or grid[0][0] == 1:\n",
    "            return -1\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        queue = collections.deque([(0,0)])\n",
    "        steps = 0\n",
    "        moves = [(1,0),(0,1),(-1,0),(0,-1),(1,1),(-1,-1),(-1,1),(1,-1)]\n",
    "        # 标记visited\n",
    "        grid[0][0] = 1\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                x,y = queue.popleft()\n",
    "                \n",
    "                if x == m-1 and y == n-1:\n",
    "                    return steps+1\n",
    "                        \n",
    "                for dx, dy in moves:\n",
    "                    nx,ny = dx + x, dy + y\n",
    "                    print(nx,ny)\n",
    "                    if nx in range(m) and ny in range(n) and grid[nx][ny] != 1 :\n",
    "                        # 标记visited\n",
    "                        grid[nx][ny] = 1\n",
    "                        queue.append((nx,ny))\n",
    "            steps+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] != 0 or grid[-1][-1] != 0:\n",
    "            return -1\n",
    "        n = len(grid)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        v = [[False]*n  for _ in  range(n)]\n",
    "        v[0][0] = True\n",
    "        q = [(0,0,1)]\n",
    "\n",
    "        for i,j,c in q:\n",
    "            for di in [-1,0,1]:\n",
    "                for dj in [-1,0,1]:\n",
    "                    ni = i + di\n",
    "                    nj = j + dj\n",
    "                    if ni == n-1 and nj == n-1:\n",
    "                        return c+1\n",
    "                    if 0<=ni<n and 0<=nj<n and not v[ni][nj] and grid[ni][nj] == 0:\n",
    "                        q.append((ni,nj,c+1))\n",
    "                        v[ni][nj] = True\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if(len(grid)==1):\n",
    "            if(grid[0][0]==0):\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "        if(grid[0][0]==1):return -1\n",
    "        state=[[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "        q=[[0,0]]\n",
    "        visited=[[False]*len(grid)for _ in range(len(grid))]\n",
    "        visited[0][0]=True\n",
    "        depth=1\n",
    "        while(q):\n",
    "            tmp_list=[]\n",
    "            for cur in q:\n",
    "                if(grid[cur[0]][cur[1]]==1):\n",
    "                    continue\n",
    "                if(cur[0]<0 or cur[1]<0 or cur[0]>=len(grid) or cur[1]>=len(grid)):\n",
    "                    continue\n",
    "                if(cur==[len(grid)-1,len(grid)-1]):\n",
    "                    return depth\n",
    "                visited[cur[0]][cur[1]]=True\n",
    "                for next in state:\n",
    "                    tmp=[cur[0]+next[0],cur[1]+next[1]]\n",
    "                    if(tmp[0]<0 or tmp[1]<0 or tmp[0]>=len(grid) or tmp[1]>=len(grid)):\n",
    "                        continue\n",
    "                    if(visited[tmp[0]][tmp[1]]==False and grid[tmp[0]][tmp[1]]==0):\n",
    "                        tmp_list.append(tmp)\n",
    "            q=self.reuse(tmp_list)\n",
    "            depth+=1\n",
    "        return -1\n",
    "    def reuse(self,arr:List[List[int]])->List[List[int]]:\n",
    "        arr0=[]\n",
    "        for item in arr:\n",
    "            if item not in arr0:\n",
    "                arr0.append(item)\n",
    "        return arr0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        if grid[0][0] != 0 or grid[-1][-1] != 0:\n",
    "            return -1\n",
    "        vis = [[0] * m for _ in range(n)]\n",
    "        q = [(0, 0)]\n",
    "        # vis[0][0] = 1\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            nxt = []\n",
    "            cnt += 1\n",
    "            for i, j in q:\n",
    "                if i < 0 or j < 0 or n == i or j == m:\n",
    "                    continue\n",
    "                if i == n-1 and j == m-1:\n",
    "                    return cnt\n",
    "                if vis[i][j] or grid[i][j]:continue\n",
    "                vis[i][j] = 1\n",
    "                for di, dj in [(-1, 0), (0, 1), (1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]:\n",
    "                    ni, nj = i+di, j+dj\n",
    "                    nxt.append((ni, nj))\n",
    "            q = nxt\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]:\n",
    "            return -1\n",
    "        \n",
    "        curr = [[0,0]]\n",
    "        n = len(grid)\n",
    "        grid[0][0] = -1\n",
    "\n",
    "        while curr and grid[-1][-1] == 0:\n",
    "            latter = []\n",
    "            while curr:\n",
    "                node = curr.pop(0)\n",
    "                i,j = node[0], node[1]\n",
    "                for di, dj in [0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]:\n",
    "                    next_i, next_j = i+di, j+dj\n",
    "                    if 0<=next_i<n and 0<=next_j<n and grid[next_i][next_j] == 0:\n",
    "                        grid[next_i][next_j] = grid[i][j]-1\n",
    "                        latter.append([next_i,next_j])\n",
    "            curr = latter\n",
    "        \n",
    "        if grid[-1][-1] == 0:\n",
    "            return -1\n",
    "        return -grid[-1][-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        if grid[0][0] != 0 or grid[-1][-1] != 0:\n",
    "            return -1\n",
    "        vis = [[0] * m for _ in range(n)]\n",
    "        q = [(0, 0)]\n",
    "        # vis[0][0] = 1\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            nxt = []\n",
    "            cnt += 1\n",
    "            for i, j in q:\n",
    "                if i < 0 or j < 0 or n == i or j == m:\n",
    "                    continue\n",
    "                if i == n-1 and j == m-1:\n",
    "                    return cnt\n",
    "                if vis[i][j] or grid[i][j]:continue\n",
    "                vis[i][j] = 1\n",
    "                for di, dj in [(-1, 0), (0, 1), (1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]:\n",
    "                    ni, nj = i+di, j+dj\n",
    "                    nxt.append((ni, nj))\n",
    "            q = nxt\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] or grid[-1][-1]:\n",
    "            return -1\n",
    "        \n",
    "        curr = [[0,0]]\n",
    "        n = len(grid)\n",
    "        grid[0][0] = -1\n",
    "\n",
    "        while curr and grid[-1][-1] == 0:\n",
    "            latter = []\n",
    "            while curr:\n",
    "                node = curr.pop(0)\n",
    "                i,j = node[0], node[1]\n",
    "                for di, dj in [0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]:\n",
    "                    next_i, next_j = i+di, j+dj\n",
    "                    if 0<=next_i<n and 0<=next_j<n and grid[next_i][next_j] == 0:\n",
    "                        grid[next_i][next_j] = grid[i][j]-1\n",
    "                        latter.append([next_i,next_j])\n",
    "            curr = latter\n",
    "\n",
    "        return -grid[-1][-1] if grid[-1][-1] else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        l1 = len(grid)\n",
    "        temp = [[l1-1,l1-1]]\n",
    "        if l1 == 1 :\n",
    "            return -2*grid[0][0] + 1\n",
    "        if grid[-1][-1] > 0:\n",
    "            return -1 \n",
    "        grid[-1][-1] = -1\n",
    "        def find(x,y):\n",
    "            temp = []\n",
    "            for i in range(max(x-1,0),min(x+2,l1)):\n",
    "                for j in range(max(y-1,0),min(y+2,l1)):\n",
    "                    if (i!=x or j!=y):\n",
    "                        if grid[i][j] == 0 :\n",
    "                            grid[i][j] = grid[x][y] - 1\n",
    "                            temp.append([i,j])\n",
    "            return temp\n",
    "        def bfs(temp):\n",
    "            while(len(temp) != 0):\n",
    "                temp1 = []\n",
    "                for point in temp:\n",
    "                    x,y = point[0],point[1]\n",
    "                    if x==0 and y==0:\n",
    "                        temp1 = []\n",
    "                        break\n",
    "                    temp1 = temp1 + find(x,y)\n",
    "                temp = temp1\n",
    "        bfs(temp)\n",
    "        if grid[0][0] >= 0 :\n",
    "            return -1\n",
    "        return -grid[0][0] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]:\n",
    "            return -1\n",
    "\n",
    "\n",
    "        directions=[(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]\n",
    "\n",
    "\n",
    "        def bfs(i,j):\n",
    "            queue = collections.deque([[i,j]])\n",
    "\n",
    "            min_path = 0\n",
    "            flag = False\n",
    "            while queue:\n",
    "                print(queue)\n",
    "                k = len(queue)\n",
    "                print(k)\n",
    "                min_path+=1\n",
    "                #print(n)\n",
    "                for _ in range(k):\n",
    "                    i,j = queue.popleft()\n",
    "                    #print(i,j)\n",
    "                    if i==m-1 and j==n-1:\n",
    "                        flag=True\n",
    "                        return min_path\n",
    "                    for di,dj in directions:\n",
    "                        new_i,new_j = i+di,j+dj\n",
    "                        #print(new_i,new_j)\n",
    "                        if 0<=new_i<m and 0<=new_j<n:\n",
    "                            #print('aa')\n",
    "                            if grid[new_i][new_j]==0 and visited[new_i][new_j]==0:\n",
    "                                visited[new_i][new_j]=1\n",
    "                                queue.append([new_i,new_j])\n",
    "\n",
    "            if not flag:\n",
    "                min_path=-1\n",
    "\n",
    "            return min_path\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        #print(m,n)\n",
    "        visited = [[0]*n for _ in range(m)]\n",
    "\n",
    "        visited[0][0]=1\n",
    "\n",
    "\n",
    "        min_path = bfs(0,0)\n",
    "        return min_path\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         if grid[i][j]==0 and not visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] == 1 or grid[n-1][n-1] == 1:\n",
    "            return -1\n",
    "\n",
    "        queue = [(0,0)]\n",
    "\n",
    "        dist = [[n*n+1 for _ in range(n)] for _ in range(n)]\n",
    "        dist[0][0] = 1\n",
    "\n",
    "        neighbors = [[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[-1,1],[1,-1],[1,1]]\n",
    "\n",
    "        while len(queue) > 0:\n",
    "            i,j = queue.pop(0)\n",
    "            if i == n-1 and j == n-1:\n",
    "                return dist[i][j] \n",
    "            for di, dj in neighbors:\n",
    "                new_i, new_j = i + di, j + dj\n",
    "                if new_i >= 0 and new_i < n and new_j >= 0 and new_j < n and grid[new_i][new_j] == 0:\n",
    "                    if dist[new_i][new_j] == n*n+1:\n",
    "                        queue.append((new_i, new_j))\n",
    "                    dist[new_i][new_j] = min(dist[new_i][new_j], 1+dist[i][j])\n",
    "\n",
    "\n",
    "        return -1 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:\n",
    "            return -1\n",
    "        if n == 1:\n",
    "            return 1 if grid[0][0] == 0 else -1\n",
    "        start = deque([(0, 0)])\n",
    "        end = deque([(n - 1, n - 1)])\n",
    "        start_seen = set(start)\n",
    "        end_seen = set(end)\n",
    "        step = 1\n",
    "\n",
    "        while start:\n",
    "            step += 1\n",
    "            for _ in range(len(start)):\n",
    "                r, c = start.popleft()\n",
    "                for nr, nc in (\n",
    "                    (r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c),\n",
    "                    (r + 1, c + 1), (r + 1, c - 1), (r - 1, c + 1), (r - 1, c - 1)\n",
    "                ):\n",
    "                    if not 0 <= nr < n or not 0 <= nc < n:\n",
    "                        continue\n",
    "                    if (nr, nc) in start_seen:\n",
    "                        continue\n",
    "                    if (nr, nc) in end_seen:\n",
    "                        return step\n",
    "                    if grid[nr][nc] == 0:\n",
    "                        start.append((nr, nc))\n",
    "                        start_seen.add((nr, nc))\n",
    "            if len(end) < len(start):\n",
    "                start, end = end, start\n",
    "                start_seen, end_seen = end_seen, start_seen\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid == [] or grid[0][0]==1:\n",
    "            return -1\n",
    "        Q = [(0,0)]\n",
    "        grid[0][0] = 1\n",
    "        n = len(grid)\n",
    "        ans = 0\n",
    "        while Q!=[]:\n",
    "            index = []\n",
    "            ans += 1\n",
    "            while Q!=[]:\n",
    "                if Q[0] == (n-1,n-1):\n",
    "                    return ans\n",
    "                (i,j) = Q[0]\n",
    "                Q.pop(0)\n",
    "                for (x,y) in [(i+1,j+1),(i+1,j),(i,j+1),(i-1,j+1),(i+1,j-1),(i-1,j),(i,j-1),(i-1,j-1)]:\n",
    "                    if x in range(n) and y in range(n) and grid[x][y] == 0 and (x,y) not in index:\n",
    "                        print(x,y)\n",
    "                        index.append((x,y))\n",
    "                        print(ans)\n",
    "                        grid[x][y] = 1\n",
    "            Q = index\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class QNode:                #优先队列结点类型\n",
    "  x,y=0,0\n",
    "  f,g,h=0,0,0\n",
    "  def __lt__(self,other):   #用于按f越小越优先出队\n",
    "    if self.f<other.f:return True\n",
    "    else:return False\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        dx=[0,0,-1,1,-1,1,-1,1]\n",
    "        dy=[-1,1,0,0,-1,-1,1,1]\n",
    "        n=len(grid)\n",
    "        if grid[0][0] or grid[n-1][n-1]:return -1\n",
    "        if n==1:return 1\n",
    "        minf=[[n*n for _ in range(0,n)] for _ in range(0,n)]\n",
    "        pqu=[]\n",
    "        e=QNode()\n",
    "        e.x,e.y=0,0\n",
    "        e.g,e.h=1,self.geth(0,0,n-1,n-1)\n",
    "        e.f=e.g+e.h\n",
    "        heapq.heappush(pqu,e)\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)\n",
    "            x,y=e.x,e.y\n",
    "            if x==n-1 and y==n-1:return e.g\n",
    "            for di in range(0,8):\n",
    "                nx,ny=x+dx[di],y+dy[di]\n",
    "                if nx>=0 and nx<n and ny>=0 and ny<n and grid[nx][ny]==0:\n",
    "                    e1=QNode()\n",
    "                    e1.x,e1.y=nx,ny\n",
    "                    e1.g=e.g+1\n",
    "                    e1.h=self.geth(nx,ny,n-1,n-1)\n",
    "                    e1.f=e1.g+e1.h\n",
    "                    if e1.f<minf[nx][ny]:\n",
    "                        minf[nx][ny]=e1.f\n",
    "                        heapq.heappush(pqu,e1)\n",
    "        return -1\n",
    "    def  geth(self,x,y,gx,gy):      #计算启发式函数值\n",
    "           return max(abs(gx-x),abs(gy-y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:\n",
    "            return -1\n",
    "        if n == 1:\n",
    "            return 1 if grid[0][0] == 0 else -1\n",
    "        start = deque([(0, 0)])  # 从左上角开始查找的队列\n",
    "        end = deque([(n - 1, n - 1)])  # 从右下角开始查找的队列\n",
    "        start_seen = set(start)  # 记录从左上角开始遇到过的格子\n",
    "        end_seen = set(end)  # 记录从右下角开始遇到过的格子\n",
    "        step = 1\n",
    "\n",
    "        while start:\n",
    "            step += 1\n",
    "            # 查找下一层畅通的格子\n",
    "            for _ in range(len(start)):\n",
    "                r, c = start.popleft()\n",
    "                for nr, nc in (\n",
    "                    (r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c),\n",
    "                    (r + 1, c + 1), (r + 1, c - 1), (r - 1, c + 1), (r - 1, c - 1)\n",
    "                ):\n",
    "                    if not 0 <= nr < n or not 0 <= nc < n:\n",
    "                        continue\n",
    "                    if (nr, nc) in start_seen:\n",
    "                        continue\n",
    "                    if (nr, nc) in end_seen:\n",
    "                        return step\n",
    "                    if grid[nr][nc] == 0:\n",
    "                        start.append((nr, nc))\n",
    "                        start_seen.add((nr, nc))\n",
    "            # 保证每次查找的都是长度较小的队列\n",
    "            if len(end) < len(start):\n",
    "                start, end = end, start\n",
    "                start_seen, end_seen = end_seen, start_seen\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1:\n",
    "            return -1\n",
    "\n",
    "        n = len(grid)\n",
    "        visited = [[False for _ in range(n)] for _ in range(n)]\n",
    "        queue = [(0, 0)]\n",
    "        visited[0][0] = True\n",
    "        cnt = 1\n",
    "        step = [[-1, 0], [-1, -1], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]\n",
    "\n",
    "        def func(x, y):\n",
    "            if 0 <= x < n and 0 <= y < n and not visited[x][y] and grid[x][y] == 0:\n",
    "                print(x,y)\n",
    "                visited[x][y] = True\n",
    "                queue.append((x, y))\n",
    "\n",
    "\n",
    "        while queue:\n",
    "            for k in range(len(queue)):\n",
    "                a, b = queue.pop(0)\n",
    "                if a == n - 1 and b == n - 1:\n",
    "                    return cnt\n",
    "                for i, j in step:\n",
    "                    func(a + i, b + j)\n",
    "            print(queue)\n",
    "            cnt += 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    " def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "  n = len(grid)\n",
    "  if grid[0][0] or grid[n-1][n-1]: return -1 # 如果起点或终点为1，直接返回-1\n",
    "  q = [(0, 0, 1)] # 队列初始化为起点和路径长度为1\n",
    "  grid[0][0] = 1 # 标记起点已访问\n",
    "  for i, j, d in q: # 遍历队列中的元素\n",
    "   if i == j == n-1: return d # 如果到达终点，返回路径长度\n",
    "   for x, y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1),(i+1,j+1),(i+1,j-1),(i-1,j+1),(i-1,j-1)]: # 遍历八个方向的邻居\n",
    "    if 0 <= x < n and 0 <= y < n and not grid[x][y]: # 如果邻居在矩阵范围内且为0\n",
    "     q.append((x, y, d+1)) # 把邻居加入队列，并更新路径长度\n",
    "     grid[x][y] = 1 # 标记邻居已访问\n",
    "  return -1 # 如果遍历完队列还没有到达终点，返回-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        q=[(0,0)]\n",
    "        qi=0\n",
    "        def legal(x,y):\n",
    "            return x>=0 and y>=0 and x<len(grid) and y<len(grid[0])\n",
    "        ans=[[-1]*len(grid[0])for _ in range(len(grid))]\n",
    "        ans[0][0]=1\n",
    "        inq=[[0]*len(grid[0])for _ in range(len(grid))]\n",
    "        if grid[0][0]!=0:\n",
    "            return -1\n",
    "        while qi<len(q):\n",
    "            now=q[qi]\n",
    "            qi+=1\n",
    "            for dx in range(-1,2):\n",
    "                for dy in range(-1,2):\n",
    "                    if dx==0 and dy==0:\n",
    "                        continue\n",
    "                    xx,yy=now[0]+dx,now[1]+dy\n",
    "                    if not legal(xx,yy):\n",
    "                        continue\n",
    "                    if grid[xx][yy]!=0:\n",
    "                        continue\n",
    "                    if ans[xx][yy]==-1 or ans[xx][yy]>=ans[now[0]][now[1]]+1:\n",
    "                        ans[xx][yy]=ans[now[0]][now[1]]+1\n",
    "                        if not inq[xx][yy]:\n",
    "                            q.append((xx,yy))\n",
    "                            inq[xx][yy]=1\n",
    "        return ans[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]==1 or grid[-1][-1]==1:\n",
    "            return -1\n",
    "        n = len(grid[0])\n",
    "        queue = [(0, 0, 1)]\n",
    "        grid[0][0] = 1\n",
    "        dir = [(-1,-1), (-1,1), (1,-1), (1,1), (-1, 0), (0, -1), (1,0), (0,1)]\n",
    "        for i, j, cnt in queue:\n",
    "            if i == n-1 and j == n-1:\n",
    "                return cnt\n",
    "            for dx, dy in dir:\n",
    "                x, y = i+dx, j+dy\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\n",
    "                    grid[x][y] = 1\n",
    "                    queue.append((x, y, cnt + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] == 1 or grid[n-1][n-1] == 1:\n",
    "            return -1\n",
    "\n",
    "        queue = [(0, 0, 1)]\n",
    "        # 走过的点标记为 1, 避免重复计算提高算法效率\n",
    "        grid[0][0] = 1\n",
    "        dir = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]\n",
    "        for i, j, cnt in queue:\n",
    "            if i == n-1 and j == n-1: \n",
    "                return cnt\n",
    "            for dx, dy in dir:\n",
    "                x, y = i+dx, j+dy\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\n",
    "                    grid[x][y] = 1\n",
    "                    queue.append((x, y, cnt+1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid) - 1\n",
    "        if grid[0][0] | grid[n][n]:\n",
    "            return -1\n",
    "        grid[0][0] = 1\n",
    "        queue = [(0, 0, 1)]\n",
    "        for x, y, d in queue:\n",
    "            if x == y == n:\n",
    "                return d\n",
    "            for dx, dy in pairwise([0, 1, 1, 0, -1, 1, -1, -1, 0]):\n",
    "                nx = x + dx\n",
    "                ny = y + dy\n",
    "                if 0 <= nx <= n and 0 <= ny <= n and grid[nx][ny] == 0:\n",
    "                    grid[nx][ny] = 1\n",
    "                    queue.append((nx, ny, d + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        size = len(grid)\n",
    "        if grid[0][0] == 1 or grid[size - 1][size - 1] == 1:\n",
    "            return -1\n",
    "\n",
    "        moves = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]\n",
    "\n",
    "        queue = [(0, 0, 1)]\n",
    "        grid[0][0] = 1\n",
    "        for s, e, n in queue:\n",
    "\n",
    "            if s == size - 1 and e == size - 1:\n",
    "                return n\n",
    "\n",
    "            for mx, my in moves:\n",
    "                x, y = s + mx, e + my\n",
    "                if 0 <= x < size and 0 <= y < size and grid[x][y] == 0:\n",
    "                    queue.append((x, y, n + 1))\n",
    "                    grid[x][y] = 1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from functools import lru_cache\r\n",
    "# from collections import deque\r\n",
    "\r\n",
    "# class Solution:\r\n",
    "#     def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\r\n",
    "#         self.n = len(grid)\r\n",
    "#         if grid[0][0] or grid[self.n-1][self.n-1]:\r\n",
    "#             return -1\r\n",
    "\r\n",
    "#         if self.n <= 2:\r\n",
    "#             return self.n\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\r\n",
    "        n = len(grid)\r\n",
    "        if grid[0][0] == 1 or grid[n-1][n-1] == 1:\r\n",
    "            return -1\r\n",
    "\r\n",
    "        if n <= 2:\r\n",
    "            return n\r\n",
    "\r\n",
    "        queue = [(0, 0, 1)]\r\n",
    "        # 走过的点标记为 1, 避免重复计算提高算法效率\r\n",
    "        grid[0][0] = 1\r\n",
    "        dir = [(-1, -1), (-1, 0), (-1, 1), (0, -1),\r\n",
    "               (0, 1), (1, -1), (1, 0), (1, 1)]\r\n",
    "        for i, j, cnt in queue:\r\n",
    "            if i == n-1 and j == n-1:\r\n",
    "                return cnt\r\n",
    "            for dx, dy in dir:\r\n",
    "                x, y = i+dx, j+dy\r\n",
    "                if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\r\n",
    "                    grid[x][y] = 1\r\n",
    "                    queue.append((x, y, cnt+1))\r\n",
    "        return -1\r\n",
    "\r\n",
    "        # # @lru_cache\r\n",
    "        # def helper(x, y):\r\n",
    "        #     if x < 0 or y < 0 or x == self.n or y == self.n or grid[x][y]:\r\n",
    "        #         return float('inf')\r\n",
    "        #     if x == self.n-1 and y == self.n-1:\r\n",
    "        #         return 1\r\n",
    "\r\n",
    "        #     p1 = helper(x+1, y)\r\n",
    "        #     p2 = helper(x, y+1)\r\n",
    "        #     p5 = helper(x+1, y+1)\r\n",
    "        #     if (minVal := min(p1, p2, p5)) < float('inf'):\r\n",
    "        #         return minVal+1\r\n",
    "\r\n",
    "        #     # 防止走回来\r\n",
    "        #     grid[x][y] = 1\r\n",
    "\r\n",
    "        #     p3 = helper(x-1, y)\r\n",
    "        #     p4 = helper(x, y-1)\r\n",
    "        #     p6 = helper(x-1, y+1)\r\n",
    "        #     p7 = helper(x-1, y-1)\r\n",
    "        #     p8 = helper(x+1, y-1)\r\n",
    "\r\n",
    "        #     grid[x][y] = 0\r\n",
    "        #     # print((x, y, (p1, p2, p3, p4, p5, p6, p7, p8)))\r\n",
    "        #     return min(minVal, p3, p4, p6, p7, p8)+1\r\n",
    "\r\n",
    "        # ret = helper(0, 0)\r\n",
    "        # return ret if ret != float('inf') else -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        # 首先解决特殊情况：图为空或图中只有一个值\n",
    "        if grid[0][0] == 1 or n == 0:\n",
    "            return -1\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        # 经过的点位全都修改为1\n",
    "        grid[0][0] = 1\n",
    "\n",
    "        direct = [(0, -1), (0, 1), (-1, -1), (-1, 0), (-1, 1), (1, -1), (1, 0), (1,1)]\n",
    "\n",
    "        log = [(0, 0, 1)]\n",
    "\n",
    "        for y, x, cnt in log:\n",
    "            if y == n-1 and x == n-1 and grid[y][x] == 1:\n",
    "                return cnt\n",
    "            for dy, dx in direct:\n",
    "                if 0 <= x + dx < n and 0 <= y + dy < n and grid[y+dy][x+dx] == 0:\n",
    "                    log.append((y+dy, x+dx, cnt+1))\n",
    "                    grid[y+dy][x+dx] = 1 # 经过的位置赋值为1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] != 0:\n",
    "            return -1\n",
    "        length = len(grid)\n",
    "        if length == 1:\n",
    "            return 1\n",
    "        que = deque()\n",
    "        visited = {}\n",
    "        que.appendleft((0,0))\n",
    "        visited[(0,0)] = True\n",
    "        start = 1\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                ind, con = que.pop()\n",
    "                for pos_h, pos_v in [(-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1)]:\n",
    "                    new_ind = ind + pos_h\n",
    "                    new_con = con + pos_v\n",
    "                    if 0 <= new_ind < length and 0 <= new_con < length and grid[new_ind][new_con] == 0 and not visited.get((new_ind, new_con)):\n",
    "                        if new_ind == length - 1 and new_con == length - 1:\n",
    "                            return start + 1\n",
    "                        que.appendleft((new_ind, new_con))\n",
    "                        visited[(new_ind, new_con)] = True\n",
    "            start += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] == 1 or grid[n-1][n-1] == 1:\n",
    "            return -1\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        visited = set()\n",
    "        queue1 = set()\n",
    "        queue2 = set()\n",
    "        queue1.add((0,0))\n",
    "        queue2.add((n-1,n-1))\n",
    "        visited.add((0,0))\n",
    "        step = 1\n",
    "        while queue1 and queue2:\n",
    "            tmp = set()\n",
    "            for i, j in queue1:\n",
    "                for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1), (i-1, j-1), (i+1,j+1), (i-1,j+1), (i+1,j-1)]:\n",
    "                    if (x, y) in queue2:\n",
    "                        return step + 1\n",
    "                    if 0 <= x < n and 0 <= y < n and (x, y) not in visited and grid[x][y] == 0:\n",
    "                        tmp.add((x, y))\n",
    "                        visited.add((x,y))\n",
    "            step += 1\n",
    "            queue1 = queue2\n",
    "            queue2 = tmp\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] != 0:\n",
    "            return -1\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        eq = collections.deque([(0, 0)])\n",
    "        distance = {(0, 0) : 1} # key: point, value: distance\n",
    "        dx = [1, 1, 1, 0, 0, -1, -1, -1]\n",
    "        dy = [-1, 0, 1, 1, -1, -1, 0, 1]\n",
    "        while eq:\n",
    "            curx, cury = eq.popleft()\n",
    "            curdis = distance[(curx, cury)]\n",
    "            for i in range(8):\n",
    "                nextx, nexty = curx + dx[i], cury + dy[i]\n",
    "                if 0 <= nextx < n and 0 <= nexty < m and (nextx, nexty) not in distance and grid[nextx][nexty] == 0:\n",
    "                    distance[(nextx, nexty)] = curdis + 1\n",
    "                    eq.append((nextx, nexty))\n",
    "        if (n - 1, m - 1) not in distance:\n",
    "            return -1\n",
    "        return distance[(n - 1, m - 1)]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] != 0:\n",
    "            return -1\n",
    "        length = len(grid)\n",
    "        if length == 1:\n",
    "            return 1\n",
    "        que = deque()\n",
    "        visited = {}\n",
    "        que.appendleft((0,0))\n",
    "        visited[(0,0)] = True\n",
    "        start = 1\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                ind, con = que.pop()\n",
    "                for pos_h, pos_v in [(-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1)]:\n",
    "                    new_ind = ind + pos_h\n",
    "                    new_con = con + pos_v\n",
    "                    if 0 <= new_ind < length and 0 <= new_con < length and grid[new_ind][new_con] == 0 and not visited.get((new_ind, new_con)):\n",
    "                        if new_ind == length - 1 and new_con == length - 1:\n",
    "                            return start + 1\n",
    "                        que.appendleft((new_ind, new_con))\n",
    "                        visited[(new_ind, new_con)] = True\n",
    "            start += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0]: return -1\n",
    "        if len(grid) == 1: return 1   #这句可以不写，长度为一，那就把判断移到弹出那里就可以，但加入队列时就判断可以更快得出答案\n",
    "        n = len(grid)\n",
    "        pairs = [(0, 1), (0, -1), (-1, 0), (1, 0), (1, 1), (1, -1), (-1, -1), (-1, 1)]\n",
    "        dic1 = {(0, 0):1}#可以记录每层节点数以此来记录层数也就是结果，也可以像这样用一个字典同时标记访问过以及层数。当然vis也可以根据题意更巧妙地标记，既然1代表不能走，那么访问过直接标记为1也是很巧妙的。还有用元组比列表更节省空间\n",
    "        queue = deque([(0, 0)])\n",
    "        res = -1\n",
    "        while queue:\n",
    "            ponit = queue.popleft()\n",
    "            path = dic1.get(ponit)\n",
    "            for a, b in pairs:\n",
    "                x = a + ponit[0]\n",
    "                y = b + ponit[1]\n",
    "                if 0 <= x < n and 0 <= y < n and not grid[x][y] and (x, y) not in dic1:\n",
    "                    if x == n - 1 and y == n - 1:\n",
    "                        return path + 1\n",
    "                    queue.append((x, y))\n",
    "                    dic1[(x, y)] = path + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] != 0:\n",
    "            return -1\n",
    "\n",
    "        length = len(grid)\n",
    "\n",
    "        if length == 1:\n",
    "            return 1\n",
    "\n",
    "        que = deque()\n",
    "        visited = {}\n",
    "        que.appendleft((0, 0))\n",
    "        visited[(0, 0)] = True\n",
    "        step = 1\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                ind, con = que.pop()\n",
    "                for pos_h, pos_v in [(-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)]:\n",
    "                    new_ind = ind + pos_h\n",
    "                    new_con = con + pos_v\n",
    "                    if 0 <= new_ind < length and 0 <= new_con < length and grid[new_ind][new_con] == 0 and not visited.get((new_ind, new_con)):\n",
    "                        if new_ind == length-1 and new_con == length-1:\n",
    "                            return step + 1\n",
    "                        que.appendleft((new_ind, new_con))\n",
    "                        visited[(new_ind, new_con)] = True\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        if grid[0][0]==1:\n",
    "            return -1\n",
    "        if n==1:\n",
    "            return 1\n",
    "        q=deque()\n",
    "        used=set()\n",
    "        q.append((0,0))\n",
    "        used.add((0,0))\n",
    "        dirs=[[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]\n",
    "        dis=1\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            dis+=1\n",
    "            for _ in range(size):\n",
    "                r,c=q.popleft()\n",
    "                for i,j in dirs:\n",
    "                    x=r+i\n",
    "                    y=c+j\n",
    "                    if 0<=x<n and 0<=y<n and (x,y) not in used and grid[x][y]==0:\n",
    "                        if (x,y)==(n-1,n-1):\n",
    "                            return dis\n",
    "                        q.append((x,y))\n",
    "                        used.add((x,y))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] != 0:\n",
    "            return -1\n",
    "\n",
    "        steps = 1\n",
    "        q = [(0, 0)]\n",
    "        visited = {(0, 0):1}\n",
    "        while q:\n",
    "            next_q = []\n",
    "            for i, j in q:\n",
    "                if i == n-1 and j == n-1:\n",
    "                    return steps\n",
    "                for ii, jj in [(i, j-1), (i, j+1), (i-1, j), (i+1, j), (i-1, j-1), (i-1, j+1), (i+1, j-1), (i+1, j+1)]:\n",
    "                    if ii < 0 or ii >= n or jj < 0 or jj >= n:\n",
    "                        continue\n",
    "                    if grid[ii][jj] != 0:\n",
    "                        continue\n",
    "                    if (ii, jj) in visited:\n",
    "                        continue\n",
    "                    visited[(ii, jj)] = 1\n",
    "                    next_q.append((ii, jj))\n",
    "            steps += 1\n",
    "            q = next_q\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] != 0:\n",
    "            return -1\n",
    "        length = len(grid)\n",
    "        if length == 1:\n",
    "            return 1\n",
    "        que = deque()\n",
    "        visited = {}\n",
    "        que.appendleft((0,0))\n",
    "        visited[(0,0)] = True\n",
    "        start = 1\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                ind, con = que.pop()\n",
    "                for pos_h, pos_v in [(-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1)]:\n",
    "                    new_ind = ind + pos_h\n",
    "                    new_con = con + pos_v\n",
    "                    if 0 <= new_ind < length and 0 <= new_con < length and grid[new_ind][new_con] == 0 and not visited.get((new_ind, new_con)):\n",
    "                        if new_ind == length - 1 and new_con == length - 1:\n",
    "                            return start + 1\n",
    "                        que.appendleft((new_ind, new_con))\n",
    "                        visited[(new_ind, new_con)] = True\n",
    "            start += 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1 or grid[-1][-1] == 1:\n",
    "            return -1\n",
    "        d = [[-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0]]\n",
    "        stack = [(0, 0)]\n",
    "        vis = set((0,0))\n",
    "        ans = 0\n",
    "        n = len(grid)\n",
    "        while stack:\n",
    "            nodes = stack\n",
    "            stack = []\n",
    "            ans += 1\n",
    "            for node in nodes:\n",
    "                if node == (n - 1, n - 1):\n",
    "                    return ans\n",
    "                for x, y in d:\n",
    "                    x += node[0]\n",
    "                    y += node[1]\n",
    "                    if (x, y) not in vis and -1 < x < n and -1 < y < n and grid[x][y] == 0:\n",
    "                        stack.append((x, y))\n",
    "                        vis.add((x, y))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] != 0:\n",
    "            return -1\n",
    "        length = len(grid)\n",
    "        if length == 1:\n",
    "            return 1\n",
    "        que = deque()\n",
    "        visited = {}\n",
    "        que.appendleft((0,0))\n",
    "        visited[(0,0)] = True\n",
    "        start = 1\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                ind, con = que.pop()\n",
    "                for pos_h, pos_v in [(-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1)]:\n",
    "                    new_ind = ind + pos_h\n",
    "                    new_con = con + pos_v\n",
    "                    if 0 <= new_ind < length and 0 <= new_con < length and grid[new_ind][new_con] == 0 and not visited.get((new_ind, new_con)):\n",
    "                        if new_ind == length - 1 and new_con == length - 1:\n",
    "                            return start + 1\n",
    "                        que.appendleft((new_ind, new_con))\n",
    "                        visited[(new_ind, new_con)] = True\n",
    "            start += 1\n",
    "        return -1\n",
    "# class Solution:\n",
    "#     def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "#         if grid[0][0]==1 or grid[-1][-1]==1:\n",
    "#             return -1\n",
    "#         n=len(grid)\n",
    "#         if n==1:\n",
    "#             return 1\n",
    "#         visited=set()\n",
    "#         visited.add((0,0))\n",
    "#         queue=collections.deque()\n",
    "#         step=1\n",
    "#         queue.append([0,0])\n",
    "#         while queue:\n",
    "#             for _ in range(len(queue)):\n",
    "#                 i,j=queue.popleft()\n",
    "#                 for offset_x in range(-1,2):\n",
    "#                     for offset_y in range(-1,2):\n",
    "#                         x=i+offset_x\n",
    "#                         y=i+offset_y\n",
    "#                         if 0<=x<n and 0<=y<n:\n",
    "#                             if (x,y) not in visited and grid[x][y]==0:\n",
    "#                                 if x==n-1 and y==n-1:\n",
    "#                                     return step+1\n",
    "#                                 visited.add((x,y))\n",
    "#                                 queue.append([x,y])\n",
    "#             step+=1\n",
    "#         return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0]!=0:\n",
    "            return -1\n",
    "\n",
    "        visited = {}\n",
    "        que = deque([(0,0)])\n",
    "        dir = [[0,1],[0,-1],[-1,0],[1,0],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "        visited[(0,0)] = True\n",
    "        step = 0\n",
    "        while que:\n",
    "            step+=1\n",
    "            for _ in range(len(que)):\n",
    "                x,y = que.popleft()\n",
    "                if x==y and y==n-1:\n",
    "                    return step\n",
    "                for dx,dy in dir:\n",
    "                    if not visited.get((x+dx,y+dy)) and 0<=x+dx<n and 0<=y+dy<n and grid[x+dx][y+dy] == 0 :\n",
    "                        que.append((x+dx,y+dy))\n",
    "                        visited[(x+dx,y+dy)] = True\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[-1][-1]==1:\n",
    "            return -1\n",
    "        n=len(grid)\n",
    "        q=deque([(0,0,1)])\n",
    "        vis={}\n",
    "        move=[(1,1),(1,0),(1,-1),(0,1),(0,-1),(-1,1),(-1,0),(-1,-1)]\n",
    "        ans=float('inf')\n",
    "        while q:\n",
    "            x,y,l=q.popleft()\n",
    "            if x==n-1 and y==n-1:\n",
    "                ans=min(ans,l)\n",
    "            if x<0 or x==n or y<0 or y==n or grid[x][y]==1 or (x,y) in vis:\n",
    "                continue\n",
    "            for i in range(8):\n",
    "                q.append((x+move[i][0],y+move[i][1],l+1))\n",
    "            vis[(x,y)]=1\n",
    "        return ans if ans!=float('inf') else -1\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1:\n",
    "            return -1\n",
    "\n",
    "        n = len(grid)\n",
    "        queue = deque([(0, 0, 1)])\n",
    "        visited = set((0, 0))\n",
    "\n",
    "        directions = [[-1, 0], [1, 0], [0, -1], [0, 1],\n",
    "                      [1, 1], [1, -1], [-1, 1], [-1, -1]]\n",
    "\n",
    "        while queue:\n",
    "            row, col, length = queue.popleft()\n",
    "            if row == n-1 and col == n-1:\n",
    "                return length\n",
    "            for r, c in directions:\n",
    "                newr, newc = row + r, col + c\n",
    "                if 0 <= newr < n and 0 <= newc < n and (newr, newc) not in visited and grid[newr][newc] == 0:\n",
    "                        queue.append((newr, newc, length+1))\n",
    "                        visited.add((newr, newc))\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] == 1 or grid[n-1][n-1] == 1:\n",
    "            return -1\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        visited = set()\n",
    "        # (x,y,length)\n",
    "        queue = collections.deque()\n",
    "        queue.append((0,0,1))\n",
    "        # (x,y)\n",
    "        visited.add((0,0))\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                x, y, length = queue.popleft()\n",
    "                # print(x, y, length)\n",
    "                if x == y == n - 1:\n",
    "                    return length\n",
    "                for i in [-1,0,1]:\n",
    "                    for j in [-1,0,1]:\n",
    "                        if i == j == 0:\n",
    "                            continue\n",
    "                        nx = x + i\n",
    "                        ny = y + j\n",
    "                        if nx < 0 or ny < 0 or nx >= n or ny >= n or grid[nx][ny] == 1:\n",
    "                            continue\n",
    "                        if (nx,ny) not in visited:\n",
    "                            queue.append((nx, ny, length + 1))\n",
    "                            visited.add((nx,ny))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = set()\n",
    "        q = [(0, 0, 1)]\n",
    "        while q:\n",
    "            x, y, d = q.pop(0)\n",
    "            if x<0 or x>=m or y<0 or y>=n or (x, y) in visited or grid[x][y] == 1:\n",
    "                continue\n",
    "            if (x, y) == (m-1, n-1):\n",
    "                return d\n",
    "            visited.add((x, y))\n",
    "            for nx, ny in [(x-1, y-1), (x-1, y), (x-1, y+1), (x, y-1), (x, y+1), (x+1, y-1), (x+1, y), (x+1, y+1)]:\n",
    "                q.append((nx, ny, d + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1:\n",
    "            return -1\n",
    "\n",
    "        self.n = len(grid)\n",
    "\n",
    "        def BFS(curX, curY, grid, visited, nextTobeVisit):\n",
    "            dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]\n",
    "            for deltaX, deltaY in dirs:\n",
    "                newX = curX + deltaX\n",
    "                newY = curY + deltaY\n",
    "                if 0 <= newX < self.n and 0 <= newY < self.n and grid[newX][newY] == 0 and (newX, newY) not in visited:\n",
    "                    nextTobeVisit.append((newX, newY))\n",
    "                    visited.add((newX, newY))\n",
    "        \n",
    "        visited = set((0, 0))\n",
    "        tobeVisit = [(0, 0)]\n",
    "        nextTobeVisit = []\n",
    "        curLen = 1\n",
    "        \n",
    "        while tobeVisit:\n",
    "            curX, curY = tobeVisit.pop()\n",
    "            if curX == self.n - 1 and curY == self.n - 1:\n",
    "                return curLen\n",
    "            BFS(curX, curY, grid, visited, nextTobeVisit)\n",
    "            \n",
    "            if not tobeVisit:\n",
    "                curLen += 1\n",
    "                tobeVisit = nextTobeVisit\n",
    "                nextTobeVisit = []\n",
    "        \n",
    "        return -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] != 0: return -1\n",
    "        q, vis = [(0, 0, 1)], set([(0, 0)])\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        while q:\n",
    "            i, j, cost = q.pop(0)\n",
    "            if i == m-1 and j == n-1:\n",
    "                return cost\n",
    "            for x, y in ((1,1), (-1,1), (1, -1), (-1, -1), (1, 0), (-1, 0), (0, 1), (0, -1)):\n",
    "                ni, nj = i+x, j+y\n",
    "                if ni<0 or nj<0 or ni>m-1 or nj>n-1 or grid[ni][nj] != 0 or (ni, nj) in vis:\n",
    "                    continue\n",
    "                q.append((ni, nj, cost+1))\n",
    "                vis.add((ni, nj))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        q = deque()\n",
    "        visited = set()\n",
    "        if grid[0][0] != 0:\n",
    "            return -1\n",
    "        q.append([(0,0), 1])\n",
    "        visited.add((0,0))\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            for i in range(l):\n",
    "                node, step = q.popleft()\n",
    "                if node == (n-1, n-1):\n",
    "                    return step\n",
    "                for direction in [(0,1), (0,-1), (1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]:\n",
    "                    x1 = node[0] + direction[0]\n",
    "                    y1 = node[1] + direction[1]\n",
    "                    if 0<=x1<=n-1 and 0<=y1<=n-1 and (x1,y1) not in visited and grid[x1][y1] == 0:\n",
    "                        visited.add((x1,y1))\n",
    "                        q.append([(x1,y1), step+1])\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "        queue = deque([(0,0,1)])\n",
    "        direct = [[0, 1], [1, 0], [0, -1], [-1, 0],\n",
    "                  [1, 1], [-1, -1], [1, -1], [-1, 1]]\n",
    "        visited = set((0,0))\n",
    "\n",
    "        while queue:\n",
    "            r,c, length = queue.popleft()\n",
    "            if (min(r,c) < 0 or max(r,c) >= N or grid[r][c] == 1):\n",
    "                continue\n",
    "            if (r == N-1 and c == N-1):\n",
    "                return length\n",
    "            for dr, dc in direct:\n",
    "                if (r+dr,c+dc) not in visited:\n",
    "                    queue.append((r+dr,c+dc,length+1))\n",
    "                    visited.add((r+dr,c+dc))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1:\n",
    "            return -1\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = set()\n",
    "        dist = [[float(\"inf\")] * n for _ in range(m)]\n",
    "        dist[0][0] = 1\n",
    "        q = [(1, 0, 0)]\n",
    "        visited.add((0, 0))\n",
    "        while q:\n",
    "            d, x, y = heapq.heappop(q)\n",
    "            if (x, y) == (m-1, n-1):\n",
    "                return d\n",
    "            for nx, ny in [(x-1, y-1), (x-1, y), (x-1, y+1), (x, y-1), (x, y+1), (x+1, y-1), (x+1, y), (x+1, y+1)]:\n",
    "                if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited and grid[nx][ny] == 0 and d + 1 <= dist[nx][ny]:\n",
    "                    visited.add((nx, ny))\n",
    "                    dist[nx][ny] = d + 1\n",
    "                    heapq.heappush(q, (dist[nx][ny], nx, ny))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1:\n",
    "            return -1\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return 1\n",
    "        visited =set()\n",
    "        q = deque()\n",
    "        q.append([(0,0), 1])\n",
    "        visited.add((0,0))\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            for i in range(l):\n",
    "                node, step = q.popleft()\n",
    "                for direction in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]:\n",
    "                    if not 0<=node[0]+direction[0]<=m-1 or not 0<=node[1]+direction[1]<=n-1:\n",
    "                        continue\n",
    "                    elif grid[node[0]+direction[0]][node[1]+direction[1]] == 0  and (node[0]+direction[0], node[1]+direction[1]) not in visited:\n",
    "                        visited.add((node[0]+direction[0], node[1]+direction[1]))\n",
    "                        q.append([(node[0]+direction[0], node[1]+direction[1]), step + 1])\n",
    "                        if (node[0]+direction[0],node[1]+direction[1]) == (m-1, n-1):\n",
    "                                return step + 1\n",
    "                    else:\n",
    "                        pass\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        if grid[0][0] == 1:\n",
    "            return -1\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return 1\n",
    "        visited =set()\n",
    "        q = deque()\n",
    "        q.append([(0,0), 1])\n",
    "        visited.add((0,0))\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            for i in range(l):\n",
    "                node, step = q.popleft()\n",
    "                for direction in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]:\n",
    "                    if not 0<=node[0]+direction[0]<=m-1 or not 0<=node[1]+direction[1]<=n-1:\n",
    "                        continue\n",
    "                    elif grid[node[0]+direction[0]][node[1]+direction[1]] == 0  and (node[0]+direction[0], node[1]+direction[1]) not in visited:\n",
    "                        visited.add((node[0]+direction[0], node[1]+direction[1]))\n",
    "                        q.append([(node[0]+direction[0], node[1]+direction[1]), step + 1])\n",
    "                        if (node[0]+direction[0],node[1]+direction[1]) == (m-1, n-1):\n",
    "                                return step + 1\n",
    "                    else:\n",
    "                        pass\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        que=[]\n",
    "        \n",
    "        visited=set((0,0))\n",
    "\n",
    "        if grid[0][0]==0 and grid[n-1][n-1]==0:\n",
    "            que.append([0,0])\n",
    "            c=0\n",
    "            while que:\n",
    "                c+=1\n",
    "                #que2=[]\n",
    "                for _ in range (len(que)):\n",
    "                #while que: \n",
    "                    y,x=que.pop(0)\n",
    "                    if y==n-1 and x==n-1:\n",
    "                        return c\n",
    "                    for i,j in [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]:\n",
    "                        if 0<=y+i<n and 0<=x+j<n and grid[y+i][x+j]==0 and (y+i,x+j) not in visited:\n",
    "                           \n",
    "                            visited.add((y+i,x+j))\n",
    "                            que.append([y+i,x+j])\n",
    "                #que=que2\n",
    "    \n",
    "        return -1\n",
    "                        \n",
    "  \n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        n = len(grid)\n",
    "        if grid[0][0] == 1 or grid[n-1][n-1] == 1:\n",
    "            return -1\n",
    "        Q = deque([(0, 0, 1)])\n",
    "\n",
    "        visited = set()\n",
    "\n",
    "        while Q:\n",
    "\n",
    "            x, y, steps = Q.popleft()\n",
    "\n",
    "            if x == n-1 and y == n-1:\n",
    "                return steps\n",
    "\n",
    "            for dx, dy in ((1, 0), (1, 1), (0, 1), (1, -1), (-1, 0), (0, -1), (-1, -1), (-1, 1)):\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited and grid[nx][ny] == 0:\n",
    "                    Q.append((nx, ny, steps+1))\n",
    "                    visited.add((nx, ny))\n",
    "\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        l = len(grid)\n",
    "        ans = 1\n",
    "        visited = set((0,0))\n",
    "        if grid[0][0] != 0 or grid[l-1][l-1] != 0:\n",
    "            return -1\n",
    "        if l == 1:\n",
    "            return 1\n",
    "        directions = [[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "        que = deque()\n",
    "        que.append((0,0))\n",
    "        while que:\n",
    "            for _ in range(len(que)): #这样遍历都忘记啦！是一个level嘛\n",
    "                cur = que.popleft()\n",
    "                print(cur)\n",
    "                for rdir, cdir in directions:\n",
    "                    new_row = cur[0]+ rdir\n",
    "                    new_col = cur[1] + cdir\n",
    "                    if 0 <= new_row < l and 0 <=new_col < l and grid[new_row][new_col] == 0 and (new_row, new_col) not in visited:\n",
    "                        if new_row == l-1 and new_col == l -1:\n",
    "                            return ans + 1\n",
    "                        que.append((new_row, new_col))\n",
    "                        visited.add((new_row, new_col))\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        if grid[0][0] or grid[-1][-1]:\n",
    "            return -1\n",
    "        if n == 1 and m == 1:\n",
    "            return 1\n",
    "\n",
    "        finded = {(0, 0)}\n",
    "        de = deque()\n",
    "        de.append((0, 0))\n",
    "        aspict = [[0, 1], [0, -1], [1, -1], [1, 1], [1, 0], [-1, 1], [-1, -1], [-1, 0]]\n",
    "\n",
    "        ans = 1\n",
    "        while de:\n",
    "            for _ in range(len(de)):\n",
    "                x, y = de.pop()\n",
    "                for a, b in aspict:\n",
    "                    a += x\n",
    "                    b += y\n",
    "                    if 0 <= a < n and 0 <= b < m and grid[a][b] == 0 and (a, b) not in finded:\n",
    "                        finded.add((a, b))\n",
    "                        de.appendleft((a, b))\n",
    "                        if a == n - 1 and b == m - 1:\n",
    "                            return ans + 1\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestPathBinaryMatrix(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if grid[-1][-1]==1 or grid[0][0]==1:\n",
    "            return -1\n",
    "        dirs=[(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1),]\n",
    "        visit=set()\n",
    "        grid[0][0]=1\n",
    "        deq=deque()\n",
    "        tlen=len(grid)\n",
    "        deq.append(((0,0),1))\n",
    "        while deq:\n",
    "            tmp=deq.popleft()\n",
    "            for dir in dirs:\n",
    "                x,y=tmp[0][0]+dir[0],tmp[0][1]+dir[1]\n",
    "                if 0<=x<tlen and 0<=y<tlen and grid[x][y]==0:\n",
    "                    visit.add((x,y))\n",
    "                    deq.append(((x,y),tmp[1]+1))\n",
    "                    grid[x][y]=tmp[1]+1\n",
    "\n",
    "        return grid[-1][-1] if grid[-1][-1]!=0 else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
